function LinkedList() {
    // head记录头指针
    this.head = null

    // 链表不同于数组，长度需要自己手动记录
    this.length = 0

    // 封装一个内部类，记录节点
    function Node(data) {
        // data保存节点的信息
        this.data = data

        // next保存指针，也就是如何到下一个节点
        this.next = null
    }

    // toString()
    LinkedList.prototype.toString = function () {
        let current = this.head
        let listString = ''

        // 对当前节点是否存在进行判断
        while (current) {
            current.next
                ? listString += current.data + '-'
                : listString += current.data
            current = current.next
        }
        return listString
    }

    // 链表追加方法
    LinkedList.prototype.append = function (data) {
        // 创建新的节点
        const newNode = new Node(data)

        // 判断原链表是否为空
        // 为空，直接更改头指针的指向
        if (this.length == 0) this.head = newNode
        // 不为空，则找到最后一个节点，让其指针指向新节点
        else {
            let current = this.head

            // 如果节点的指向不为undefined，则current变成下个节点
            while (current.next) current = current.next
            current.next = newNode
        }

        // 链表长度+1
        this.length++
    }

    // 链表插入
    LinkedList.prototype.insert = function (position, data) {
        // 对要插入的位置进行一个越界判断
        if (position < 0 || position > this.length) return false

        const newNode = new Node(data)

        // 如果插入的位置在第0项，则要修改this.head的指向
        if (position == 0) {
            current.next = this.head
            this.head = current
        }
        else {
            // 如果不是，则通过循环找到要插入的位置，
            // 将前一个节点的指针指向新节点
            // 将新节点的指针指向原来位置的节点
            let previous = null// 记录前一个节点
            let current = this.head
            let index = 0// 作为找到position的循环判断媒介
            while (index++ < position) {
                previous = current
                current = current.next
            }
            previous.next = newNode
            newNode.next = current
        }
        // 注意长度+1
        this.length++
        return true
    }

    // 根据位置获取节点内容
    LinkedList.prototype.get = function (position) {
        // 越界判断
        if (position < 0 || position >= this.length) return null
        let current = this.head
        let index = 0

        // 通过循环找到position处的节点
        while (index++ < position) current = current.next
        return current.data
    }

    // 根据内容查找第一次出现的位置
    LinkedList.prototype.indexOf = function (data) {
        let current = this.head
        let index = 0// 记录位置信息
        while (current) {
            if (current.data == data) return index
            current = current.next
            index++
        }
        return -1//找不到就返回“-1”
    }

    // 更新元素
    LinkedList.prototype.update = function (position, content) {
        if (position < 0 || position >= this.length) return false
        let index = 0
        let current = this.head

        // 当找到节点后，修改当前节点的data
        while (index++ < position) current = current.next
        current.data = content
        return true
    }

    // 从链表某一位置移除一项元素
    LinkedList.prototype.removeAt = function (position) {
        if (position < 0 || position >= this.length) return false
        let current = this.head // 保存当前项元素
        let previous = null // 保存当前项元素的上一项元素

        // 当移除的是第一项元素时，修改头指针的指向
        if (position == 0) this.head = current.next
        else {
            let index = 0
            while (index++ < position) {
                previous = current
                current = current.next
            }
            // 当找到要删除的元素后，将它的上一项元素的指针指向它的下一项元素
            previous.next = current.next
        }

        // 因为删除了一项元素，注意长度-1
        this.length--
        return true
    }

    LinkedList.prototype.remove = function (data) {
        // 调用indexOf方法，根据data获得元素的position
        const index = this.indexOf(data)

        // 调用removeAt方法，根据position移除元素
        return this.removeAt(index)

    }
}

let ll = new LinkedList()
ll.append(10)
ll.append('bbb')
ll.append('aaa')
// console.log(ll)
// console.log(ll.toString())
ll.insert(1, '#')
ll.insert(4, '###')
// console.log(ll.toString())
// console.log(ll.get(2))
// console.log(ll.get(4))
// console.log(ll.get(5))
// console.log(ll.get(0))
// console.log(ll.indexOf('###'))
// console.log(ll.indexOf('##'))
ll.update(1, '***')
console.log(ll.toString())
// ll.removeAt(2)
// console.log(ll.toString())
// ll.removeAt(0)
// console.log(ll.toString())
console.log(ll.remove('###'))
console.log(ll.toString())
console.log(ll.remove('bbb'))
console.log(ll.toString())

